package xin.luna.algorithm;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

public class BinarySearch {
  private static int binarySearch(int[] whitelist, int key) {
    if (whitelist.length <= 0) {
      return -1;
    }

    int mid = whitelist.length / 2;

    if (key == whitelist[mid]) {
      return mid;
    } else if (key < whitelist[mid]) {
      return binarySearch(Arrays.copyOfRange(whitelist, 0, mid), key);
    } else {
      return binarySearch(Arrays.copyOfRange(whitelist, mid + 1, whitelist.length), key);
    }
  }

  public static void main(String[] args) {
    In in = new In(args[0]);
    int[] whitelist = in.readAllInts();
    Arrays.sort(whitelist);

    while (!StdIn.isEmpty()) {
      int search = StdIn.readInt();

      if (binarySearch(whitelist, search) < 0) {
        StdOut.println(search);
      }
    }
  }
}
